public class Solution980 {

    int ans=0;
    int[] dx=new int[]{0,1,0,-1};
    int[] dy=new int[]{1,0,-1,0};

    public int uniquePathsIII(int[][] grid) {
        int total=0;
        int[] start=null;
        int[] end=null;
        for (int i=0;i<grid.length;i++) {
            for (int j=0;j<grid[0].length;j++) {
                if (grid[i][j]==0){
                    total++;
                }else if (grid[i][j]==1){
                    start=new int[]{i,j};
                }else if (grid[i][j]==2){
                    end=new int[]{i,j};
                }
            }
        }
        total++;
        int[][] visit=new int[grid.length][grid[0].length];
        visit[start[0]][start[1]]=1;
        dfs(start,0,total,end,visit,grid);
        return ans;
    }

    private void dfs(int[] now, int k, int total, int[] end, int[][] visit, int[][] grid) {
        if (now[0]==end[0] && now[1]==end[1]){
            if (k==total){
                ans++;
            }
            return;
        }
        for (int i=0;i<4;i++){
            int x=now[0]+dx[i];
            int y=now[1]+dy[i];
            if (x>=0 && x<grid.length && y>=0 && y<grid[0].length && grid[x][y]!=-1 && visit[x][y]!=1){
                visit[x][y]=1;
                dfs(new int[]{x,y},k+1,total,end,visit,grid);
                visit[x][y]=0;
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution980().uniquePathsIII(new int[][]{{1,0,0,0},{0,0,0,0},{0,0,2,-1}}));
    }
}
